NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/5416

Internet Message Format | 1996-08-05 | 4.4 KB

Path: cs.utexas.edu!not-for-mail
From: [e-mail] (Paul Wilson)
Newsgroups: comp.lang.lisp,comp.lang.c++,comp.lang.c,comp.lang.misc
Subject: GC & traditional allocators & textbooks
Date: 4 Feb 1996 09:16:58 -0600
Organization: CS Dept, University of Texas at Austin
Message-ID: <4f2ila$[e-mail]>
References: <[e-mail]> <[e-mail]> <4eu5l9$[e-mail]> <[e-mail]>
NNTP-Posting-Host: jive.cs.utexas.edu

In article <[e-mail]>,
Cyber Surfer  <[e-mail]> wrote:
>In article <4eu5l9$[e-mail]>
>           [e-mail] "Paul Wilson" writes:
>
>> >If you want to know about basic
>> >garbage collecting, I'd recommend a computer science book, as it'll
>> >probably be more up to date.
>>
>> I have to disagree here.  I know of no textbooks with even a decent
>> discussion of garbage collection. [...]
>
>Was I refering to modern GC? I'm not sure. I don't know of any books
>on modern GC, but a book 20 years old seems to contain GC techniques
>that many C/C++ programmers are unaware of. Even if that's the best
>book on the subject, it could still enlighten a few programmers.

OK, agreed.  There are some fundamental algorithms that *are* in some
textbooks and should be better known.

On the other hand, even some of the textbooks that do discuss the
fundamental algorithms often propagate naive views about GC that are rather
damaging.  (Henry Baker, Hans Boehm, and I have all put a fair amount
of effort into trying to slow the spread of those myths on the net.)

This is also true of traditional allocators.  The history of allocator
research has been a big mess---the literature is a bit of a disaster
area---and the textbooks reflect this.  The analyses in the books are
shallow and largely wrong.  (This is less attributable to the textbooks
authors than the weak discussions of GC.  It's not their fault that they
can't summarize the gist of the literature and get it right, because
the literature in general is disorganized, inconsistent, and often wrong.)

One of the problems in the area of traditional memory allocators is that
people have taken one particular textbook far too seriously---Volume 1
of Knuth's _The_Art_of_Computer_Programming_.  It was written in 1968,
and some of it has turned out to be less than helpful.  It's still the
standard reference, though, and other textbook writers often regurgitate
its discussion of memory allocators.  Implementors often look at it and
go and implement things that have been known to be bad since the early
1970's.  (Knuth is still tremendously influential in allocator work,
despite the fact that he doesn't appear to have written anything about it
in over 25 years.  This is not Knuth's fault, of course---inertia makes
the world go 'round.)

"Modified First Fit" with the roving pointer is the clearest example.  It
was a bad idea, and it was quickly shown to be bad, but some other textbook
writers keep mindlessly cribbing from Knuth, and even some implementors still
use it.

Obligatory positive comment:  the best textbook discussion of allocators
that I know of is Tim Standish's in _Data_Structure_Techniques_.  He doesn't
recognize the near-universal methodological problems with allocator studies,
but he's unique in recognizing the basic data structure and algorithm issues
in implementing allocators.

>> I suggest looking at the papers on our web site (in my .sig, below) which
>> include two surveys (long and medium-sized) on GC.  (The long version will
>> appear in Computing Surveys after some revision.)

This site also has our big survey on memory allocators from IWMM '95, which
I hope will influence future textbooks.  It talks about empirical methodology
as well as giving a fairly exhaustive treatment of implementation techniques.

>> There are also several
>> other papers there by my research group and a bunch by other people
>> (from the '91 and '93 OOPSLA GC workshops), and a big bibliography in
>> LaTeX .bib format.  The web page also has links to Henry Baker's and Hans
>> Boehm's web pages.


--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin ([e-mail])
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and  Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)